<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Binomial Coefficients</title>
<link rel="stylesheet" href="../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Math Toolkit 4.2.1">
<link rel="up" href="../factorials.html" title="Factorials and Binomial Coefficients">
<link rel="prev" href="sf_falling_factorial.html" title="Falling Factorial">
<link rel="next" href="../sf_beta.html" title="Beta Functions">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="sf_falling_factorial.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../factorials.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../sf_beta.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="math_toolkit.factorials.sf_binomial"></a><a class="link" href="sf_binomial.html" title="Binomial Coefficients">Binomial Coefficients</a>
</h3></div></div></div>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">special_functions</span><span class="special">/</span><span class="identifier">binomial</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
</pre>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">k</span><span class="special">);</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">T</span><span class="special">,</span> <span class="keyword">class</span> <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&gt;</span>
<span class="identifier">T</span> <span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="keyword">unsigned</span> <span class="identifier">n</span><span class="special">,</span> <span class="keyword">unsigned</span> <span class="identifier">k</span><span class="special">,</span> <span class="keyword">const</span> <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&amp;);</span>

<span class="special">}}</span> <span class="comment">// namespaces</span>
</pre>
<p>
        Returns the binomial coefficient: <sub>n</sub>C<sub>k</sub>.
      </p>
<p>
        Requires k &lt;= n.
      </p>
<p>
        The final <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">Policy</a> argument is optional and can
        be used to control the behaviour of the function: how it handles errors,
        what level of precision to use etc. Refer to the <a class="link" href="../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">policy
        documentation for more details</a>.
      </p>
<p>
        May return the result of <a class="link" href="../error_handling.html#math_toolkit.error_handling.overflow_error">overflow_error</a>
        if the result is too large to represent in type T.
      </p>
<div class="important"><table border="0" summary="Important">
<tr>
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Important]" src="../../../../../../doc/src/images/important.png"></td>
<th align="left">Important</th>
</tr>
<tr><td align="left" valign="top">
<p>
          The functions described above are templates where the template argument
          <code class="computeroutput"><span class="identifier">T</span></code> can not be deduced from
          the arguments passed to the function. Therefore if you write something
          like:
        </p>
<p>
          <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">binomial_coefficient</span><span class="special">(</span><span class="number">10</span><span class="special">,</span> <span class="number">2</span><span class="special">);</span></code>
        </p>
<p>
          You will get a compiler error, usually indicating that there is no such
          function to be found. Instead you need to specify the return type explicitly
          and write:
        </p>
<p>
          <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">math</span><span class="special">::</span><span class="identifier">binomial_coefficient</span><span class="special">&lt;</span><span class="keyword">double</span><span class="special">&gt;(</span><span class="number">10</span><span class="special">,</span> <span class="number">2</span><span class="special">);</span></code>
        </p>
<p>
          So that the return type is known. Further, the template argument must be
          a real-valued type such as <code class="computeroutput"><span class="keyword">float</span></code>
          or <code class="computeroutput"><span class="keyword">double</span></code> and not an integer
          type - that would overflow far too easily!
        </p>
</td></tr>
</table></div>
<h5>
<a name="math_toolkit.factorials.sf_binomial.h0"></a>
        <span class="phrase"><a name="math_toolkit.factorials.sf_binomial.accuracy"></a></span><a class="link" href="sf_binomial.html#math_toolkit.factorials.sf_binomial.accuracy">Accuracy</a>
      </h5>
<p>
        The accuracy will be the same as for the factorials for small arguments (i.e.
        no more than one or two epsilon), and the <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>
        function for larger arguments.
      </p>
<h5>
<a name="math_toolkit.factorials.sf_binomial.h1"></a>
        <span class="phrase"><a name="math_toolkit.factorials.sf_binomial.testing"></a></span><a class="link" href="sf_binomial.html#math_toolkit.factorials.sf_binomial.testing">Testing</a>
      </h5>
<p>
        The spot tests for the binomial coefficients use data generated by <a href="http://www.wolframalpha.com/" target="_top">Wolfram Alpha</a>.
      </p>
<h5>
<a name="math_toolkit.factorials.sf_binomial.h2"></a>
        <span class="phrase"><a name="math_toolkit.factorials.sf_binomial.implementation"></a></span><a class="link" href="sf_binomial.html#math_toolkit.factorials.sf_binomial.implementation">Implementation</a>
      </h5>
<p>
        Binomial coefficients are calculated using table lookup of factorials where
        possible using:
      </p>
<div class="blockquote"><blockquote class="blockquote"><p>
          <span class="serif_italic"><span class="emphasis"><em><sub>n</sub>C<sub>k</sub> = n! / (k!(n-k)!)</em></span></span>
        </p></blockquote></div>
<p>
        Otherwise it is implemented in terms of the beta function using the relations:
      </p>
<div class="blockquote"><blockquote class="blockquote"><p>
          <span class="serif_italic"><span class="emphasis"><em><sub>n</sub>C<sub>k</sub> = 1 / (k * <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>(k,
          n-k+1))</em></span></span>
        </p></blockquote></div>
<p>
        and
      </p>
<div class="blockquote"><blockquote class="blockquote"><p>
          <span class="serif_italic"><span class="emphasis"><em><sub>n</sub>C<sub>k</sub> = 1 / ((n-k) * <a class="link" href="../sf_beta/beta_function.html" title="Beta">beta</a>(k+1,
          n-k))</em></span></span>
        </p></blockquote></div>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
      Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
      Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
      Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
      Walker and Xiaogang Zhang<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="sf_falling_factorial.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../factorials.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="../sf_beta.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
